//2009.使数组连续的最少操作数
//https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-continuous/description/
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        //红黑树排序+去重 效率较低
        //set<int> cnt(nums.begin(),nums.end());

        //哈希去重 排序
        // unordered_set<int> cnt(nums.begin(),nums.end());
        // vector<int> v(cnt.begin(),cnt.end());
        // sort(v.begin(),v.end());

        //去重+排序 效率较高
        vector<int> v(nums.begin(),nums.end());
        sort(v.begin(),v.end());
        vector<int>::iterator it = unique(v.begin(),v.end());
        int num = 0;
        while(it+num != v.end()) ++num; //计算重复数字数量
        int sz = n-num; //去重后的数字数量
        v.resize(sz);
        //最大操作次数是n-1 方便操作下 默认为n
        int ret = n;
        int k = 0;
        //控制最小数
        for(int i = 0;i<sz && k<sz;++i)
        {
            //排序数中 i是最小的 以i为最小值时的最大数
            int maxn = v[i]+n-1;
            //如果当前数小于最大数 则无需操作 更新操作次数
            //如果当前数不在该区间中 则必为单独的一个区间 需要调整 (当i==j时n-1为最大值) 该值需要调整
            //例如 1 2 3 5 6
            //以1作为最小值时 一个五个数 right = 1+5-1 = 5
            //所以前五个数会被跳过 (因为在区间中) 遍历到6时跳出 此时j=4
            //i遍历到下标4以前都不会进入while
            //当到4时 i==j 此时6需要调整(为4) res不更新 所以res最终为1
            //前面1 2 3 5 每个数都在区间中 当j移动时 j-i区间表示不需要操作的区间
            //j-i变大 则操作次数变小
            while(k < sz && v[k] <= maxn)
            {
                ret = min(ret,n-(k-i+1));
                ++k; //k继续遍历后面的数
            }
        }
        return ret;
    }
};